package company.tree;

import java.util.LinkedList;

/**
 * 题目如下：
 * 随机给定一棵树，求树中总共的节点个数
 *
 * 思路：
 * （1）定义一个计数器和一个队列（先进先出）
 * （2）先将树的根节点放入队列中，下面执行循环，当队列不为空时，循环一直执行
 * （3）在循环体当中，首先取出队列中的元素，再让result++，后面判断该节点是否有左子节点，如果有就让左子节点入队列；再判断该节点是否有右子节点，如果有们就让右子节点入队列；
 * （4）当队列不为空时，一直执行循环，树的节点都会放入到队列当中，而每一次循环都会在队列中取出一个数据并让result++；
 * （5）直到循环结束，result表示曾经进入到队列的数据个数，即树的节点个数。
 * 注：
 * 当所有节点都入队列之后，循环体当中起作用的功能其实只有取出一个队列中的数据再让result++。
 *
 * 代码如下：
 *
 */
public class TreeByLevel {
    TreeNode root;
    public static void main(String[] args) {
        TreeByLevel tree = new TreeByLevel();
        tree.insertDiGui(tree.root, 10);
        tree.insertDiGui(tree.root, 18);
        tree.insertDiGui(tree.root, 3);
        tree.insertDiGui(tree.root, 8);
        tree.insertDiGui(tree.root, 12);
        tree.insertDiGui(tree.root, 2);
        tree.insertDiGui(tree.root, 7);
        tree.insertDiGui(tree.root, 4);
        System.out.println("先序遍历：");
        tree.beforeOrder(tree.root);

        System.out.println("节点个数："+findNodeNum(tree.root));
    }

    public static int findNodeNum(TreeNode root) {
        //定义计数器
        int result=0;
        //定义队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        //将根节点放入队列当中
        queue.add(root);
        while (!queue.isEmpty()) {//当队列不为空时，执行循环
            root = queue.pop();//取出一个队列中的元素，就让result++，直到队列为空，不执行循环
            result++;
            if (root.getLeft() != null) {//如果节点的左子节点不为空
                queue.add(root.getLeft());//将该节点的左子节点入队列
            }
            if (root.getRight() != null) {//如果节点的右子节点不为空
                queue.add(root.getRight());//将该节点的右子节点入队列
            }
        }
        return result;
    }
    //递归构建有序二叉树
    public void insertDiGui(TreeNode node, int value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
            return;
        }

        if (node.getValue() > newNode.getValue()) {
            if (node.getLeft() != null) {
                insertDiGui(node.getLeft(), value);
            } else {
                node.setLeft(newNode);
            }
        } else {
            if (node.getRight() != null) {
                insertDiGui(node.getRight(), value);
            } else {
                node.setRight(newNode);
            }
        }
    }

    //先序遍历
    public void beforeOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.getValue() + " ");
        beforeOrder(node.getLeft());
        beforeOrder(node.getRight());
    }
}
